#include <stddef.h>  // For size_t
#include <stdlib.h>  // For qsort and malloc/free
#include <stdio.h>
#include <string.h> // 用于memcpy

// 交换两个整数的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heap_sort_int(int* arr, size_t len) {
    if (!arr || len == 0) return;

    for (size_t i = len / 2 - 1; i != (size_t)-1; --i) {
        for (size_t j = i; (j * 2 + 1) < len; ) {
            size_t k = j * 2 + 1;
            if ((k + 1) < len && arr[k] < arr[k + 1]) {
                ++k;
            }
            if (arr[j] < arr[k]) {
                swap(&arr[j], &arr[k]);
                j = k;
            } else {
                break;
            }
        }
    }

    for (size_t i = len - 1; i > 0; --i) {
        swap(&arr[0], &arr[i]);
        for (size_t j = 0; (j * 2 + 1) < i; ) {
            size_t k = j * 2 + 1;
            if ((k + 1) < i && arr[k] < arr[k + 1]) {
                ++k;
            }
            if (arr[j] < arr[k]) {
                swap(&arr[j], &arr[k]);
                j = k;
            } else {
                break;
            }
        }
    }
}

void shell_sort_int(int* arr, size_t len) {
    if (!arr || len == 0) return;

    for (size_t gap = len / 3; gap > 0; gap /= 3) {
        for (size_t i = gap; i < len; ++i) {
            int temp = arr[i];
            size_t j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

void merge_sort_int(int* arr, size_t len) {
    if (!arr || len <= 1) return;

    if (len == 2) {
        if (arr[0] > arr[1]) {
            swap(&arr[0], &arr[1]);
        }
        return;
    }

    size_t mid = len / 2;
    merge_sort_int(arr, mid);
    merge_sort_int(arr + mid, len - mid);

    int* temp = (int*)malloc(len * sizeof(int));
    if (!temp) return; // 内存分配失败

    size_t i = 0, j = mid, k = 0;
    while (i < mid && j < len) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i < mid) temp[k++] = arr[i++];
    while (j < len) temp[k++] = arr[j++];

    for (size_t t = 0; t < len; ++t) {
        arr[t] = temp[t];
    }

    free(temp);
}

int compare_ints(const void* a, const void* b) {
    int int_a = *((int*)a);
    int int_b = *((int*)b);

    // 返回值为负表示int_a小于int_b，0表示相等，正表示int_a大于int_b
    return (int_a > int_b) - (int_a < int_b);
}

void quick_sort_int(int* arr, size_t len) {
    if (!arr || len == 0) return;
    qsort(arr, len, sizeof(int), compare_ints);
}